package avl_tree

import (
	"go-guide/utils/intefaces"
)

// 平衡二叉树
type AVLTree struct {
	root *node
}

type node struct {
	left  *node
	right *node
	val   interface{}
	// 树的高度
	height int
	// 子树的节点个数
	size int
}

func NewAVLTree() *AVLTree {
	return &AVLTree{
		root: nil,
	}
}

func (avl *AVLTree) Add(e interface{}) {
	avl.root = avl.add(avl.root, e)
}

// 判断一个树是否为平衡二叉树
func (avl *AVLTree) balanced() bool {
	return false
}

func (avl *AVLTree) Height() int {
	return 0
}

func height(node *node) int {
	if node == nil {
		return -1
	}
	return node.height
}

func size(node *node) int {
	return node.size
}

// 对节点y进行向左旋转操作，返回旋转后新的根节点x
//    y                             x
//  /  \                          /   \
// T1   x      向左旋转 (y)       y     z
//     / \   - - - - - - - ->   / \   / \
//   T2  z                     T1 T2 T3 T4
//      / \
//     T3 T4

func rotateLeft(y *node) *node {
	return nil
}

// 对节点y进行向右旋转操作，返回旋转后新的根节点x
//        y                              x
//       / \                           /   \
//      x   T4     向右旋转 (y)        z     y
//     / \       - - - - - - - ->    / \   / \
//    z   T3                       T1  T2 T3 T4
//   / \
// T1   T2
func rotateRight(y *node) *node {
	return nil
}

func balance(n *node) *node {
	if balanceFactor(n) < -1 {
		if balanceFactor(n.right) > 0 {
			n.right = rotateRight(n.right)
		}
		n = rotateLeft(n)
	} else if balanceFactor(n) > 1 {
		if balanceFactor(n.left) < 0 {
			n.left = rotateLeft(n.left)
		}
		n = rotateRight(n.left)
	}
	return n
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func (avl *AVLTree) add(n *node, e interface{}) *node {
	if n == nil {
		return &node{
			left:   nil,
			right:  nil,
			val:    e,
			height: 0,
			size:   1,
		}
	}
	if intefaces.Compare(e, n.val) > 0 {
		n.right = avl.add(n.right, e)
	} else {
		n.left = avl.add(n.left, e)
	}
	n.size = 1 + size(n.left) + size(n.right)
	n.height = 1 + max(height(n.left), height(n.right))
	return balance(n)
}

func balanceFactor(n *node) int {
	return height(n.left) - height(n.right)
}

// 判断一个树是否为平衡二叉树
func IsAVL(x *node) bool {
	if x == nil {
		return true
	}
	bf := balanceFactor(x)

	if bf > 1 || bf < -1 {
		return false
	}
	return IsAVL(x.left) && IsAVL(x.right)
}
